#include <iostream>
#include <windows.h>

struct Node
{
	int iRow;
	int iCol;
	int akList[9];

	Node* pkPrev;
};
int main()
{
	DWORD dwTime = GetTickCount();
	Node* pkCurr = 0;
	int akSudoku[9][9] = 
	{
		{0,0,0,0,6,1,0,0,5},
		{0,3,0,0,0,0,0,0,9},
		{0,4,0,0,0,3,1,0,0},
		{7,8,0,3,0,0,0,5,2},
		{0,0,2,0,0,0,9,0,0},
		{5,9,0,0,0,8,0,1,6},
		{0,0,7,1,0,0,0,9,0},
		{6,0,0,0,0,0,0,7,0},
		{9,0,0,6,2,0,0,0,0},
	};

	while (true)
	{
		int iTempRow = 0;
		int iTempCol = 0;
		int iSize = 9;
		int akTempSet[9] = {0};

		
		for(int iRow = 0;iRow < 9;++iRow)
		{
			for (int iCol = 0;iCol < 9;++iCol)
			{
				if(akSudoku[iRow][iCol])
				{
					continue;
				}
				int akTemp[9] = {0};
				for(int i= 0;i < 9;++i)
				{
					if(akSudoku[i][iCol])
					{
						akTemp[akSudoku[i][iCol] - 1] = 1;
					}
					if(akSudoku[iRow][i])
					{
						akTemp[akSudoku[iRow][i] - 1] = 1;
					}
					int iH = iRow / 3 * 3 + i / 3;
					int iW = iCol / 3 * 3 + i % 3;

					if(akSudoku[iH][iW])
					{
						akTemp[akSudoku[iH][iW] - 1] = 1;
					}
				}

				int iCount = 0;
				for(int i = 0;i < 9;++i)
				{
					if(!akTemp[i])
					{
						++iCount;
					}
				}
				if(!iCount)
				{
					while(true)
					{
						if(pkCurr)
						{
							for(int iNumber = 0;iNumber < 9;++iNumber)
							{
								if(!pkCurr->akList[iNumber])
								{
									akSudoku[pkCurr->iRow][pkCurr->iCol] = iNumber + 1;
									pkCurr->akList[iNumber] = 1;
									goto Continue;
								}
							}

							akSudoku[pkCurr->iRow][pkCurr->iCol] = 0;

							Node* pkNode = pkCurr;
							pkCurr = pkNode->pkPrev;
							delete pkNode;
						}
						else
						{
							goto Error;
						}
					}
				}

				if(iCount < iSize)
				{
					iTempRow = iRow;
					iTempCol = iCol;
					iSize = iCount;

					memcpy(&akTempSet[0],&akTemp[0],sizeof(int) * 9);
				}
			}
		}
		if(iSize == 9)
		{
			goto Succ;
		}

		Node* pkNode = new Node;

		pkNode->iRow = iTempRow;
		pkNode->iCol = iTempCol;

		memcpy(&pkNode->akList[0],&akTempSet[0],sizeof(int) * 9);
		pkNode->pkPrev = pkCurr;
		pkCurr = pkNode;

		for(int iIndex = 0;iIndex < 9;++iIndex)
		{
			if(pkNode->akList[iIndex] == 0)
			{
				akSudoku[iTempRow][iTempCol] = iIndex + 1;
				pkNode->akList[iIndex] = 1;
				break;
			}
		}

Continue:
		continue;
Error:
		std::cout<<"Error"<<std::endl;
		break;
Succ:
		for(int iRow = 0;iRow < 9;++iRow)
		{
			for (int iCol = 0;iCol < 9;++iCol)
			{
				std::cout<<akSudoku[iRow][iCol]<<",";
			}
			std::cout<<std::endl;
		}
		break;
	}

	std::cout<<std::endl<<GetTickCount() - dwTime<<std::endl;


	while(pkCurr)
	{
		Node* pkNode = pkCurr;
		pkCurr = pkCurr->pkPrev;
		delete pkNode;
	}

	system("pause");
	return 0;
}